package com.xuzz.study.datastructure;

public class SingleLinkedList {
    public class Node{
        Object data;
        Node next;
        public Node(Object data)
        {
            this.data = data;
        }
    }

    private int size;
    public Node head;
    public SingleLinkedList()
    {
        this.size = 0 ;
        this.head = null;
    }

    public void display()
    {
        System.out.println("");
        if(size>0)
        {
            System.out.print("[");
            Node node = head;
            while(null!=node)
            {
                System.out.print(node.data+"->");
                node = node.next;
            }
            System.out.print("]");
        }
        else
        {
            System.out.println("[]");
        }
    }
    public boolean isEmpty(){
        return size==0?true:false;
    }

    /**
     * 头部插入元素
     * @param data
     * @return
     */
    public Object addHead(Object data)
    {
        Node newHead = new Node(data);
        if(size==0)
        {
            head = newHead;
        }
        else
        {
            newHead.next = head;
            head=newHead;
        }
        size++;
        return data;
    }

    public Object add(Object data)
    {
        Node newNode = new Node(data);
        if(size==0)
        {
            head=newNode;
        }
        else {
            Node tmp = head;
            while(null!=tmp.next)
            {
                tmp=tmp.next;
            }
            tmp.next=newNode;
        }
        size++;
        return data;
    }

    /**
     * 删除头结点
     * @return
     */
    public Object deleteHead()
    {
        if(size==0)
        {
            return null;
        }
        Object obj = head.data;
        if(null==head.next)
        {
            head=null;
        }
        else {
            head = head.next;
        }
        size--;
        return obj;
    }

    public boolean exists(Object data)
    {
        if(size==0)
        {
            return false;
        }

        Node cur = head;
        while(null!=cur)
        {
            if(cur.data.equals(data))
            {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public Object delete(Object data)
    {
        if(size==0)
        {
            return null;
        }

        Node cur = head;
        Node pre = null;

        while(null!=cur)
        {
            if(cur.data.equals(data))
            {
                if(cur==head)
                {
                    this.deleteHead();
                }
                else
                {
                    pre.next=cur.next;
                }
                return data;
            }
            else {
                pre = cur;
            }
            cur = cur.next;
        }

        return null;
//
//        while(!cur.data.equals(data))
//        {
//            if(null==cur.next)
//            {
//                return null;
//            }
//
//            pre = cur;
//            cur = cur.next;
//        }
//
//        if(cur==head)
//        {
//            this.deleteHead();
//        }
//        else
//        {
//            pre.next=cur.next;
//            size--;
//        }
//        return data;
    }

    /**
     * 反转
     * @return
     */
    public Node reverse()
    {
        if(size==0)
        {
            return null;
        }
        if(size==1)
        {
            return head;
        }
        Node cur = head;
        Node pre = null;
        Node tmp = null;
        while(null!=cur)
        {
            tmp = cur.next;
            cur.next=pre;
            pre = cur;
            cur = tmp;
        }
        head=  pre;
        return head;

       /* Node cur2 = head;
        // 1->2->3->4
        // cur2=1 header=1 t = 2
        //
        while(null!=cur2.next)
        {
            Node t = cur2.next;
            cur2.next=t.next;
            t.next=head;
            head=t;
        }*/
    }

    public Node findMiddle()
    {
        if(size==0)
        {
            return null;
        }
        Node slow=head,fast=head;
        while(null!=fast &&null!=fast.next)
        {
            slow = slow.next;
            fast=fast.next.next;
        }
        return slow;
    }

    public boolean hasCircle()
    {
        if(size<2)
        {
            return false;
        }
        Node slow=head,fast=head.next.next;

        if(null!=fast)
        {
            if(slow.equals(fast))
            {
                return true;
            }
            slow=slow.next;
            fast = fast.next.next;
        }
//        Node slow=head,fast=head;
//        while(null!=slow && null!=fast && null!=fast.next)
//        {
//            slow = slow.next;
//            fast = fast.next.next;
//            if(slow.equals(fast))
//            {
//                return true;
//            }
//        }
        return false;
    }

    public Node oddEvenList() {

        if(null==head || null==head.next)
        {
            return head;
        }
        Node odd = head; //奇数节点
        Node even = head.next;  //偶数节点
        Node tempEven = even;
        while(odd.next!=null && even.next!=null)
        {
            if(even.next!=null)
            {
                odd.next=even.next;
                odd=odd.next;
            }
            else{
                odd.next=null;
            }

            if(odd.next!=null)
            {
                even.next=odd.next;
                even = even.next;
            }
            else
            {
                even.next = null;
            }
        }
        odd.next=tempEven;
        return head;
    }
}
